#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

    定义/definitions:
        chess_board: 整个棋盘

        grid: board中一个(3*3)的小棋盘
        grid_idx: 一个(row, col)坐标位于哪个小棋盘(对小棋盘从0开始编号)

        grid_width: 一个小棋盘的边长: 默认是3
        top_width: 一个大棋盘的边长: 是小棋盘的平方


        slot: 棋盘中的一个坐标格子(row, col), 任何两个slot的坐标都不同.
"""

import sys
import math
import copy
from pprint import pprint

import random
from collections import defaultdict


class SolveOrder:
    def __init__(self, solve_order_lst):
        self.cur_idx = 0
        self.solve_order_lst = solve_order_lst
        print("=================== len =====================", self.len())

    def next(self):
        ret = self.solve_order_lst[self.cur_idx]
        self.cur_idx += 1
        return ret

    def fallback(self):
        # 和next相对的, 后退一步: 用于递归回溯时恢复程序中状态
        self.cur_idx -= 1
        assert self.cur_idx >= 0

    def is_end(self):
        return self.cur_idx == self.len()

    def is_end_idx(self, idx):
        return idx == self.len()

    def len(self):
        return len(self.solve_order_lst)

    def idx(self, index):
        return self.solve_order_lst[index]


class Board:

    def __init__(self, grid_width=3):
        self.has_inited = False

        self.GridWidth = grid_width
        self.TopWidth = self.GridWidth ** 2

        # l = list(range(1, self.TopWidth+1))
        # random.shuffle(l)                 # 这里没用, 传入set的值会排序, 不随机
        self.total_ava_space = set( range(1, self.TopWidth+1) )

        self.total_num = self.TopWidth * self.TopWidth
        self.fixed_num = 0

        self.chess_board = self.make_board()

        self.row_occupied_nums  = defaultdict(set)      # row_num : occupiedilable__nums
        self.col_occupied_nums  = defaultdict(set)
        self.grid_occupied_nums = defaultdict(set)

        self.remain_pos = self.make_all_remain_pos()

        self.solve_order_obj = None                     # 留待后面 init_fixed()时再初始化
        self.assert_test()

    def make_board(self):
        slot = 0
        one_row = [ copy.deepcopy(slot) for i in range(self.TopWidth)]
        matrix = [ copy.deepcopy(one_row) for i in range(self.TopWidth)]
        return matrix

    def make_all_remain_pos(self):
        s = set()
        for r in range(self.TopWidth):
            for c in range(self.TopWidth):
                s.add((r, c))

        return s

    def init_fixed(self, fixed_list):
        # support only called once: 只能调用一次
        if self.has_inited:
            raise Exception("inited")

        self.has_inited = True

        for row, col, value in fixed_list:
            self.set_slot(row-1, col-1, value)

        # self.fixed_num = len(fixed_list)

    # 设置slot和其它相应"状态"
    def set_slot(self, row, col, value):
        if value > self.TopWidth or value < 1:
            raise Exception("fail set_slot value", value)

        grid_idx = self.loc_grid_idx(row,col)
        self.chess_board[row][col] = value

        if value in self.row_occupied_nums[row]:
            raise Exception("row [%s] already has value [%s]" % (row, value))

        if value in self.col_occupied_nums[col]:
            raise Exception("col [%s] already has value [%s]" % (col, value))

        if value in self.grid_occupied_nums[grid_idx]:
            raise Exception("grid [%s] already has value [%s]" % (grid_idx, value))

        self.row_occupied_nums[row].add(value)
        self.col_occupied_nums[col].add(value)
        self.grid_occupied_nums[grid_idx].add(value)

        self.remain_pos.remove( (row, col) )
        self.fixed_num += 1

    def clear_slot(self, row, col, value):
        self.chess_board[row][col] = 0

        self.row_occupied_nums[row].remove(value)
        self.col_occupied_nums[col].remove(value)
        grid_idx = self.loc_grid_idx(row,col)
        self.grid_occupied_nums[grid_idx].remove(value)

        self.remain_pos.add( (row, col) )
        self.fixed_num -= 1


        # ------------------- assert: 下面assert在9*9的大棋盘中是正确的 ---------------------

    def assert_test(self):
        if self.GridWidth == 3:
            assert self.loc_grid_idx(0,0) == 0
            assert self.loc_grid_idx(2,2) == 0

            assert self.loc_grid_idx(3,3) == 4
            assert self.loc_grid_idx(5,5) == 4

            assert self.loc_grid_idx(6,6) == 8
            assert self.loc_grid_idx(8,8) == 8

        if self.GridWidth == 2:
            assert self.loc_grid_idx(0,0) == 0
            assert self.loc_grid_idx(1,1) == 0

            assert self.loc_grid_idx(2,2) == 1
            assert self.loc_grid_idx(3,3) == 1


        print("asert loc_grid_idx() ok!")

    # 计算这个坐标在哪个sub(GridWidth * GridWidth)棋盘中
    def loc_grid_idx(self, row, col):
        # return row // self.GridWidth * (self.TopWidth / self.GridWidth) + col // self.GridWidth
        return row // self.GridWidth * self.GridWidth + col // self.GridWidth

    def show_board(self):
        digit_len = len(str(self.TopWidth))
        print()

        for row in range(self.TopWidth):
            for col in range(self.TopWidth):
                wid_s = "%" + str(digit_len) + "s,"
                print(wid_s % self.chess_board[row][col], sep=',', end='')
                if (col + 1) % self.GridWidth == 0:
                    print('|', end='')

            # print((digit_len-1) * "\n")
            print()
            if (row + 1) % self.GridWidth == 0:
                print('_' * (self.TopWidth * 3) * digit_len)

        print()
        # pprint(self.chess_board)

    def run(self):
        sys.setrecursionlimit(len(self.remain_pos) + 100)

        if self.unfixed_num == 0:
            print("Maybe you have inited all slots, Has no unfixed slots!")
            return

        self.solve_order_obj = SolveOrder(self.sort_solve_order())
        self.seted = []
        self.try_cnt = 0


        has_solution = self.recursive_try()
        print("seted>", self.seted)
        print()
        print("allll>", self.solve_order_obj.solve_order_lst)       # 保持和self.seted可以对的上.
        print("tryed count ", self.try_cnt)
        return has_solution

    # 使用默认参数, 避免顶层调用陷入细节中!
    def recursive_try(self, cur_try_pos_idx=0):
        if self.solve_order_obj.is_end_idx(cur_try_pos_idx):
            return True

        cur_try_pos = self.solve_order_obj.idx(cur_try_pos_idx)

        self.try_cnt += 1
        output_cnt = 10000 * 100     # 10w
        if self.try_cnt % output_cnt == 0: print("try_cnt", self.try_cnt)
        # print("try ", cur_try_pos, cur_try_pos_idx)

        row, col = cur_try_pos
        grid_idx = self.loc_grid_idx(row, col)

        cur_slot_availa_nums = self.slot_availa_solutions(row, col, grid_idx)

        next_try_pos_idx = cur_try_pos_idx + 1

        for cad_num in cur_slot_availa_nums:
            self.set_slot(row, col, cad_num)

            if self.recursive_try(next_try_pos_idx):
                self.seted.insert(0, cur_try_pos)
                return True
            else:
                self.clear_slot(row, col, cad_num)

        # print("total failed", cur_try_pos)
        # 当 cur_try_pos_idx 由参数传入, 在栈中维护时, 用户可以避免维护相关联的状态.减少心智负担!
        # self.solve_order_obj.fallback()
        return False

    def slot_availa_solutions(self, row, col, grid_idx):
        occuiped_row = self.row_occupied_nums[row]
        occuiped_col = self.col_occupied_nums[col]
        occuiped_grid = self.grid_occupied_nums[grid_idx]

        total_occiped = occuiped_row.union(occuiped_col, occuiped_grid)

        ava_nums = self.total_ava_space.difference(total_occiped)
        # return ava_nums

        l = list(ava_nums)
        random.shuffle(l)
        return l

    # 计算求解顺序: 从可选空间最小的pos开始
    def sort_solve_order(self):
        tmp_row_occupied_nums  = copy.deepcopy(self.row_occupied_nums)
        tmp_col_occupied_nums  = copy.deepcopy(self.col_occupied_nums)
        tmp_grid_occupied_nums = copy.deepcopy(self.grid_occupied_nums)
        tmp_remain_pos    = copy.deepcopy(self.remain_pos)
        print("remain", len(tmp_remain_pos))

        # def ava_space_num(row, col):
        #     grid_idx = self.loc_grid_idx(row, col)
        #     m = max(len(tmp_row_occupied_nums[row]), len(tmp_col_occupied_nums[col]), len(tmp_grid_occupied_nums[grid_idx]))
        #     assert m != self.TopWidth
        #     return self.TopWidth - m        # 可选的数有9个, 除去m个以后

        # def min_price_pos_1():
        #     min_pos = (None, None)
        #     min_space = 99999999999           # 很大

        #     assert tmp_remain_pos
        #     for cad_pos in tmp_remain_pos:
        #         cad_space_num = ava_space_num(cad_pos[0], cad_pos[1])
        #         if cad_space_num < min_space:
        #             min_space = cad_space_num
        #             min_pos = cad_pos

        #     return min_pos, min_space

        def occupy_space_2(row, col):
            grid_idx = self.loc_grid_idx(row, col)
            m = sum([len(tmp_row_occupied_nums[row]), len(tmp_col_occupied_nums[col]), len(tmp_grid_occupied_nums[grid_idx])])
            return m

        def occupy_space(row, col):
            grid_idx = self.loc_grid_idx(row, col)
            ts = tmp_row_occupied_nums[row].union(tmp_col_occupied_nums[col], tmp_grid_occupied_nums[grid_idx])
            return len(ts)

        def min_price_pos():
            max_pos = (None, None)
            max_occupy = -1           # 很大

            assert tmp_remain_pos
            for cad_pos in tmp_remain_pos:
                cad_occupy_num = occupy_space(cad_pos[0], cad_pos[1])
                # cad_occupy_num = occupy_space_2(cad_pos[0], cad_pos[1])       # 明显比较慢
                if cad_occupy_num > max_occupy:
                    max_occupy = cad_occupy_num
                    max_pos = cad_pos

            return max_pos, max_occupy

        # def random_append(order, ele):
        #     if len(order) < 2:
        #         order.append(ele)
        #         return
        #     else:
        #         idx = random.randint(1,2)
        #         order.insert(idx, ele)

        order = []
        for i in range(self.unfixed_num):
            next_pos, choose_space = min_price_pos()
            # next_pos, choose_space = min_price_pos_1()
            order.append(next_pos)
            row, col = next_pos

            tmp_row_occupied_nums[row].add((row, col))
            tmp_col_occupied_nums[col].add((row, col))

            grid_idx = self.loc_grid_idx(row, col)
            tmp_grid_occupied_nums[grid_idx].add((row, col))

            tmp_remain_pos.remove(next_pos)

        print("order ", order)
        print("len ", len(order))

        for i in range(self.TopWidth):
            if len(tmp_grid_occupied_nums[i]) != self.TopWidth:
                print("grid", i, len(tmp_grid_occupied_nums[i]))

            assert len(tmp_grid_occupied_nums[i]) == self.TopWidth

            if len(tmp_col_occupied_nums[i]) != self.TopWidth:
                print("col", i, len(tmp_col_occupied_nums[i]))
                print("col", i, tmp_col_occupied_nums[i])

            assert len(tmp_col_occupied_nums[i]) == self.TopWidth
            assert len(tmp_row_occupied_nums[i]) == self.TopWidth

        return order



    @property
    def unfixed_num(self):
        return self.total_num - self.fixed_num


def get_fixed_slots(file_name=""):
    if file_name == "":
        file_name = "./lst.txt"

    lst = []

    with open(file_name) as file:
        for line in file:
            line = line.strip()
            if line == '':
                continue

            # 支持注释
            if line.startswith("#"):
                print(line)
                continue

            nums = list(map(int, line.split(' ')))
            lst.append(nums)

    return lst


class Solution:
    def __init__(self):
        grid_width = 3
        # grid_width = 4
        # grid_width = 5
        board = Board(grid_width)

        simplest_lst = [ ]
        steps = grid_width * (grid_width-1)
        print('steps', steps)

        for i in range(grid_width):
            for j in range(grid_width):
                num = i*grid_width+j+1

                simplest_lst.append( (i+1, j+1, num) )
                # simplest_lst.append( (i+steps+1, j+steps+1, num) )      # 左上角grid和左下角grid保持相同
                simplest_lst.append( (i+steps+1, j+steps+1, grid_width**2 - num + 1) )      # 左上角grid和左下角grid保持相同


        board.init_fixed (
            # get_fixed_slots("./lst_world_difficult.txt")
            get_fixed_slots()
            # simplest_lst
        )

        # 如果不做init(), 就相当于随机生成整个数独board
        has_solution = board.run()
        board.show_board()
        if has_solution:
            print("\n!Got one perfect solution for sudo game!")

        has_solution = board.run()



def test():
    s = Solution()

def main():
    test()

if __name__ == "__main__":
    main()
